package com.felix.algorithms.tree;

import com.felix.algorithms.list.SequenceStack;
import com.felix.algorithms.list.Stack;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * BinaryTree
 *
 * @author xuejinhua
 * @date 2018/9/10 15:06
 */
public class BinaryTree<T> implements BinaryTreeInterface<T>, java.io.Serializable {
    /**
     * 树根结点
     */
    private BinaryNodeInterface<T> root;


    private class InOrderIterator implements Iterator<T> {

        /**
         * 定义一个顺序栈nodeStack来存放遍历过程中遇到的结点
         * list包中有顺序栈的实现
         */
        private Stack<BinaryNodeInterface<T>> nodeStack;
        private BinaryNodeInterface<T> currentNode;

        public InOrderIterator() {
            nodeStack = new SequenceStack<BinaryNodeInterface<T>>();
            //此处为什么需要强制转换呢？
            currentNode = root;
        }

        /**
         * 按照中序遍历的逻辑进行实现Iterator接口中的方法，从而实现一个迭代器
         *
         * @return
         */
        @Override
        public boolean hasNext() {
            return !nodeStack.empty() || currentNode != null;
        }

        @Override
        public T next() {
            BinaryNodeInterface<T> nextNode;
            while (currentNode != null) {
                nodeStack.push(currentNode);
                currentNode = currentNode.getLeftChild();
            }
            if (!nodeStack.empty()) {
                nextNode = nodeStack.pop();
                assert nextNode != null;
                currentNode = nextNode.getRightChild();
                return nextNode.getData();
            } else {
                throw new NoSuchElementException();
            }
        }

        /**
         * 仅仅是完成遍历的功能，删除功能是不需要有的。
         */
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

    }

    public BinaryTree() {
        root = null;
    }

    public BinaryTree(T rootData) {
        root = new BinaryNode<T>(rootData);
    }

    public BinaryTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
        privateSetTree(rootData, leftTree, rightTree);
    }

    @Override
    public void setTree(T rootData) {
        root = new BinaryNode<T>(rootData);
    }

    @Override
    public void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> rightTree) {
        privateSetTree(rootData, (BinaryTree<T>) leftTree, (BinaryTree<T>) rightTree);
    }

    private void privateSetTree(T rootData, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
        root = new BinaryNode<T>(rootData);
        if (leftTree != null && !leftTree.isEmpty()) {
            root.setLeftChild(leftTree.root);
        }
        if (rightTree != null && !rightTree.isEmpty()) {
            if (rightTree != leftTree) {
                root.setRightChild(rightTree.root);
            } else {
                root.setRightChild(rightTree.root.copy());
            }
        }
        if (leftTree != null && leftTree != this) {
            leftTree.clear();
        }
        if (rightTree != null && rightTree != this) {
            rightTree.clear();
        }
    }

    /**
     * 更改根结点的数据域
     *
     * @param rootData
     */
    protected void setRootData(T rootData) {
        root.setData(rootData);
    }

    /**
     * 更改根结点
     *
     * @param rootNode
     */
    protected void setRootNode(BinaryNodeInterface<T> rootNode) {
        root = rootNode;
    }

    @Override
    public T getRootData() {
        T rootData = null;
        if (this.root != null) {
            rootData = root.getData();
        }
        return rootData;
    }

    @Override
    public int getHeight() {
        return this.root.getHeight();
    }

    @Override
    public int getNumberOfNodes() {
        return this.root.getNumberOfNodes();
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public void clear() {
        root = null;
    }

    public void inOrderTraverse() {
        inOrderTraverse(root);
    }

    private void inOrderTraverse(BinaryNodeInterface<T> node) {
        if (node != null) {
            inOrderTraverse(node.getLeftChild());
            inOrderTraverse(node.getRightChild());
        }
    }

    public void preOrderTraverse() {
        preOrderTraverse(root);
    }

    private void preOrderTraverse(BinaryNodeInterface<T> node) {
        if (node != null) {
            preOrderTraverse(node.getLeftChild());
            preOrderTraverse(node.getRightChild());
        }
    }

    public void postOrderTraverse() {
        postOrderTraverse(root);
    }

    private void postOrderTraverse(BinaryNodeInterface<T> node) {
        if (node != null) {
            postOrderTraverse(node.getLeftChild());
            postOrderTraverse(node.getRightChild());
        }
    }

    @Override
    public Iterator<T> getPreOrderIterator() {
        return null;
    }

    @Override
    public Iterator<T> getPostOrderIterator() {
        return null;
    }

    @Override
    public Iterator<T> getInOrderIterator() {
        return new InOrderIterator();
    }

    @Override
    public Iterator<T> getLevelOrderIterator() {
        return null;
    }
}
